package com.ruoyi.system.util.deepseek;

import java.util.Arrays;

public class LevenshteinDistance {

    public static int calculate(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];

        for (int i = 0; i <= str1.length(); i++) {
            for (int j = 0; j <= str2.length(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(str1.charAt(i - 1), str2.charAt(j - 1)),
                            dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1);
                }
            }
        }

        return dp[str1.length()][str2.length()];
    }

    private static int costOfSubstitution(char a, char b) {
        return a == b ? 0 : 1;
    }

    private static int min(int... numbers) {
        return Arrays.stream(numbers).min().orElse(Integer.MAX_VALUE);
    }

    public  double similarity(String str1, String str2) {
        int maxLength = Math.max(str1.length(), str2.length());
        if (maxLength == 0) return 1.0;
        return 1.0 - (double) calculate(str1, str2) / maxLength;
    }

//    public static void main(String[] args) {
//        String str1 = "我叫王凯利，家住在潍坊安丘";
////        String str2 = "我住在山东省潍坊市安丘，叫王凯利";70
//        System.out.println("Similarity: " + similarity(str1, str2));
//    }
}
